#include <stdio.h>
int binsearch(int x, int v[], int n);
int binsearch2(int x, int v[], int n);
int binsearch3(int x, int v[], int n);
int binsearch4(int x, int v[], int n);
int main()
{
  int sorted_ary[] = {1,
				  2,
				  3,
				  4,
				  5,
				  6,
				  7,
				  8,
				  9,
				  10,
				  11,
				  74,
				  132,
				  132,
				  137,
				  210,
				  216,
				  227,
				  231,
				  311,
				  330,
				  367,
				  431,
				  436,
				  455,
				  496,
				  502,
				  519,
				  546,
				  552,
				  573,
				  579,
				  637,
				  683,
				  693,
				  703,
				  732,
				  739,
				  740,
				  792,
				  827,
				  892,
				  962,
				  1015,
				  1062,
				  1063,
				  1078,
				  1083,
				  1099,
				  1110,
				  1124,
				  1165,
				  1193,
				  1200,
				  1218,
				  1229,
				  1286,
				  1289,
				  1289,
				  1296,
				  1300,
				  1302,
				  1310,
				  1313,
				  1326,
				  1353,
				  1372,
				  1383,
				  1429,
				  1454,
				  1455,
				  1464,
				  1472,
				  1481,
				  1515,
				  1578,
				  1588,
				  1604,
				  1620,
				  1627,
				  1653,
				  1700,
				  1741,
				  1790,
				  1857,
				  1953,
				  1982,
				  2023,
				  2049,
				  2073,
				  2077,
				  2120,
				  2127,
				  2128,
				  2137,
				  2160,
				  2172,
				  2193,
				  2212,
				  2228,
				  2250,
				  2300,
				  2347,
				  2396,
				  2405,
				  2437,
				  2440,
				  2477,
				  2484,
				  2618,
				  2734,
				  2739,
				  2749,
				  2856,
				  2900,
				  2967,
				  2973,
				  2991,
				  3022,
				  3039,
				  3050,
				  3083,
				  3100,
				  3163,
				  3172,
				  3177,
				  3213,
				  3231,
				  3241,
				  3275,
				  3288,
				  3289,
				  3319,
				  3406,
				  3417,
				  3473,
				  3502,
				  3521,
				  3548,
				  3568,
				  3614,
				  3615,
				  3657,
				  3664,
				  3719,
				  3779,
				  3808,
				  3813,
				  3823,
				  3848,
				  3902,
				  3918,
				  3930,
				  3939,
				  3949,
				  3965,
				  3977,
				  4010,
				  4018,
				  4094,
				  4110,
				  4148,
				  4152,
				  4180,
				  4265,
				  4271,
				  4282,
				  4309,
				  4331,
				  4373,
				  4374,
				  4410,
				  4414,
				  4485,
				  4576,
				  4584,
				  4589,
				  4592,
				  4675,
				  4676,
				  4677,
				  4715,
				  4719,
				  4772,
				  4823,
				  4827,
				  4846,
				  4874,
				  4881,
				  4906,
				  4968,
				  4976,
				  5031,
				  5077,
				  5083,
				  5115,
				  5178,
				  5251,
				  5265,
				  5308,
				  5335,
				  5365,
				  5409,
				  5417,
				  5507,
				  5523,
				  5537,
				  5549,
				  5600,
				  5615,
				  5649,
				  5667,
				  5686,
				  5764,
				  5792,
				  5795,
				  5799,
				  5822,
				  5843,
				  5885,
				  5910,
				  5926,
				  6049,
				  6069,
				  6116,
				  6157,
				  6200,
				  6203,
				  6211,
				  6324,
				  6406,
				  6515,
				  6521,
				  6551,
				  6573,
				  6587,
				  6606,
				  6629,
				  6708,
				  6720,
				  6763,
				  6850,
				  6881,
				  6930,
				  6955,
				  6979,
				  7063,
				  7100,
				  7210,
				  7216,
				  7283,
				  7339,
				  7350,
				  7363,
				  7399,
				  7413,
				  7435,
				  7449,
				  7449,
				  7455,
				  7469,
				  7496,
				  7524,
				  7577,
				  7578,
				  7578,
				  7601,
				  7604,
				  7626,
				  7713,
				  7749,
				  7766,
				  7808,
				  7810,
				  7827,
				  7837,
				  7948,
				  7962,
				  7966,
				  7996,
				  8017,
				  8056,
				  8092,
				  8151,
				  8189,
				  8204,
				  8225,
				  8227,
				  8228,
				  8231,
				  8239,
				  8323,
				  8351,
				  8356,
				  8364,
				  8370,
				  8387,
				  8402,
				  8408,
				  8421,
				  8444,
				  8447,
				  8466,
				  8468,
				  8580,
				  8630,
				  8671,
				  8694,
				  8729,
				  8812,
				  8815,
				  8822,
				  8826,
				  8855,
				  8924,
				  8955,
				  9006,
				  9008,
				  9027,
				  9065,
				  9077,
				  9107,
				  9153,
				  9157,
				  9184,
				  9188,
				  9191,
				  9207,
				  9286,
				  9319,
				  9358,
				  9377,
				  9466,
				  9491,
				  9527,
				  9547,
				  9592,
				  9641,
				  9656,
				  9745,
				  9828,
				  9834,
				  9837,
				  9840,
				  9869,
				  9895,
				  9916,
				  9925,
				  9943,
				  9957,
				  9963,
				  10019,
				  10066,
				  10083,
				  10095,
				  10114,
				  10156,
				  10168,
				  10259,
				  10276,
				  10428,
				  10435,
				  10461,
				  10509,
				  10540,
				  10578,
				  10597,
				  10624,
				  10647,
				  10664,
				  10757,
				  10762,
				  10785,
				  10797,
				  10803,
				  10813,
				  10822,
				  10844,
				  10847,
				  10859,
				  10910,
				  10990,
				  11065,
				  11091,
				  11119,
				  11125,
				  11313,
				  11315,
				  11534,
				  11622,
				  11633,
				  11677,
				  11730,
				  11757,
				  11801,
				  11809,
				  11931,
				  11965,
				  11965,
				  11994,
				  11996,
				  11998,
				  12097,
				  12098,
				  12133,
				  12146,
				  12160,
				  12209,
				  12215,
				  12289,
				  12338,
				  12354,
				  12382,
				  12391,
				  12395,
				  12409,
				  12441,
				  12478,
				  12489,
				  12497,
				  12507,
				  12520,
				  12544,
				  12549,
				  12608,
				  12741,
				  12790,
				  12896,
				  12901,
				  13084,
				  13094,
				  13115,
				  13115,
				  13157,
				  13206,
				  13269,
				  13316,
				  13375,
				  13393,
				  13435,
				  13435,
				  13440,
				  13454,
				  13504,
				  13512,
				  13537,
				  13583,
				  13590,
				  13616,
				  13621,
				  13632,
				  13638,
				  13668,
				  13732,
				  13787,
				  13826,
				  13831,
				  13848,
				  13855,
				  13881,
				  13885,
				  13918,
				  13971,
				  13988,
				  14025,
				  14031,
				  14107,
				  14179,
				  14190,
				  14195,
				  14259,
				  14315,
				  14321,
				  14350,
				  14396,
				  14401,
				  14410,
				  14417,
				  14425,
				  14450,
				  14451,
				  14537,
				  14654,
				  14655,
				  14658,
				  14786,
				  14800,
				  14808,
				  14826,
				  14876,
				  14888,
				  14925,
				  14956,
				  14960,
				  14996,
				  15063,
				  15102,
				  15110,
				  15150,
				  15163,
				  15165,
				  15170,
				  15173,
				  15176,
				  15210,
				  15211,
				  15212,
				  15341,
				  15347,
				  15370,
				  15419,
				  15421,
				  15465,
				  15508,
				  15525,
				  15684,
				  15701,
				  15740,
				  15774,
				  15780,
				  15825,
				  15840,
				  15845,
				  15881,
				  15883,
				  15886,
				  15904,
				  15925,
				  15992,
				  16013,
				  16071,
				  16071,
				  16112,
				  16132,
				  16141,
				  16163,
				  16188,
				  16255,
				  16282,
				  16412,
				  16419,
				  16423,
				  16426,
				  16474,
				  16509,
				  16522,
				  16573,
				  16592,
				  16596,
				  16627,
				  16649,
				  16708,
				  16717,
				  16745,
				  16767,
				  16792,
				  16844,
				  16859,
				  16889,
				  16889,
				  16903,
				  16917,
				  16942,
				  17023,
				  17036,
				  17069,
				  17080,
				  17140,
				  17246,
				  17302,
				  17346,
				  17357,
				  17409,
				  17420,
				  17421,
				  17454,
				  17464,
				  17512,
				  17617,
				  17673,
				  17767,
				  17808,
				  17847,
				  17875,
				  17899,
				  17925,
				  17952,
				  17972,
				  18055,
				  18083,
				  18102,
				  18105,
				  18169,
				  18240,
				  18243,
				  18244,
				  18250,
				  18334,
				  18365,
				  18371,
				  18399,
				  18452,
				  18494,
				  18498,
				  18504,
				  18539,
				  18559,
				  18624,
				  18716,
				  18783,
				  18871,
				  18872,
				  18888,
				  18889,
				  18893,
				  18901,
				  18959,
				  18987,
				  19017,
				  19039,
				  19070,
				  19102,
				  19141,
				  19146,
				  19158,
				  19185,
				  19220,
				  19243,
				  19267,
				  19338,
				  19351,
				  19373,
				  19493,
				  19744,
				  19754,
				  19764,
				  19772,
				  19827,
				  19834,
				  19880,
				  19894,
				  19939,
				  19963,
				  19971,
				  20034,
				  20048,
				  20050,
				  20050,
				  20116,
				  20197,
				  20210,
				  20227,
				  20245,
				  20285,
				  20308,
				  20323,
				  20363,
				  20381,
				  20531,
				  20571,
				  20595,
				  20675,
				  20695,
				  20700,
				  20728,
				  20759,
				  20782,
				  20789,
				  20817,
				  20837,
				  20869,
				  20912,
				  20919,
				  20943,
				  21046,
				  21050,
				  21075,
				  21076,
				  21119,
				  21129,
				  21136,
				  21156,
				  21181,
				  21203,
				  21206,
				  21223,
				  21281,
				  21345,
				  21354,
				  21375,
				  21411,
				  21456,
				  21489,
				  21615,
				  21642,
				  21674,
				  21724,
				  21726,
				  21729,
				  21733,
				  21736,
				  21748,
				  21836,
				  21896,
				  21937,
				  21965,
				  21984,
				  21999,
				  22027,
				  22050,
				  22054,
				  22125,
				  22161,
				  22176,
				  22216,
				  22306,
				  22323,
				  22350,
				  22365,
				  22367,
				  22376,
				  22383,
				  22396,
				  22412,
				  22424,
				  22448,
				  22451,
				  22516,
				  22535,
				  22561,
				  22596,
				  22637,
				  22688,
				  22703,
				  22713,
				  22771,
				  22820,
				  22874,
				  22894,
				  22925,
				  22933,
				  22962,
				  22963,
				  22972,
				  23010,
				  23016,
				  23258,
				  23274,
				  23360,
				  23367,
				  23384,
				  23430,
				  23446,
				  23480,
				  23571,
				  23703,
				  23703,
				  23735,
				  23761,
				  23805,
				  23887,
				  23950,
				  24009,
				  24088,
				  24097,
				  24107,
				  24132,
				  24143,
				  24176,
				  24207,
				  24226,
				  24255,
				  24274,
				  24363,
				  24386,
				  24389,
				  24392,
				  24394,
				  24410,
				  24478,
				  24496,
				  24567,
				  24578,
				  24635,
				  24636,
				  24658,
				  24703,
				  24705,
				  24739,
				  24883,
				  24909,
				  24916,
				  24938,
				  24976,
				  24978,
				  24987,
				  25031,
				  25142,
				  25144,
				  25227,
				  25312,
				  25316,
				  25344,
				  25351,
				  25376,
				  25489,
				  25502,
				  25502,
				  25509,
				  25559,
				  25656,
				  25680,
				  25697,
				  25720,
				  25789,
				  25898,
				  25921,
				  25926,
				  25999,
				  26006,
				  26025,
				  26045,
				  26052,
				  26158,
				  26162,
				  26195,
				  26266,
				  26304,
				  26371,
				  26373,
				  26455,
				  26456,
				  26474,
				  26544,
				  26614,
				  26637,
				  26647,
				  26685,
				  26686,
				  26706,
				  26712,
				  26716,
				  26722,
				  26824,
				  26867,
				  26895,
				  26986,
				  27009,
				  27016,
				  27016,
				  27059,
				  27078,
				  27110,
				  27124,
				  27157,
				  27168,
				  27181,
				  27192,
				  27213,
				  27286,
				  27306,
				  27308,
				  27401,
				  27465,
				  27522,
				  27575,
				  27642,
				  27665,
				  27670,
				  27722,
				  27760,
				  27795,
				  27801,
				  27827,
				  27849,
				  27870,
				  27877,
				  27883,
				  27891,
				  27984,
				  27993,
				  28025,
				  28075,
				  28108,
				  28118,
				  28124,
				  28132,
				  28139,
				  28149,
				  28219,
				  28317,
				  28320,
				  28342,
				  28375,
				  28443,
				  28476,
				  28490,
				  28492,
				  28506,
				  28536,
				  28578,
				  28591,
				  28602,
				  28660,
				  28661,
				  28685,
				  28780,
				  28808,
				  28820,
				  28897,
				  28947,
				  29024,
				  29032,
				  29073,
				  29095,
				  29118,
				  29204,
				  29224,
				  29233,
				  29246,
				  29348,
				  29369,
				  29380,
				  29449,
				  29479,
				  29503,
				  29510,
				  29570,
				  29658,
				  29662,
				  29665,
				  29675,
				  29677,
				  29718,
				  29719,
				  29813,
				  29849,
				  29859,
				  29869,
				  29908,
				  29963,
				  29973,
				  30007,
				  30011,
				  30050,
				  30066,
				  30067,
				  30107,
				  30175,
				  30203,
				  30206,
				  30230,
				  30232,
				  30270,
				  30292,
				  30346,
				  30372,
				  30406,
				  30407,
				  30416,
				  30435,
				  30451,
				  30486,
				  30522,
				  30532,
				  30557,
				  30586,
				  30589,
				  30627,
				  30642,
				  30718,
				  30732,
				  30748,
				  30791,
				  30809,
				  30845,
				  30875,
				  30890,
				  30893,
				  30906,
				  30939,
				  30941,
				  30954,
				  31000,
				  31009,
				  31040,
				  31044,
				  31047,
				  31054,
				  31077,
				  31090,
				  31149,
				  31160,
				  31214,
				  31227,
				  31264,
				  31269,
				  31362,
				  31459,
				  31488,
				  31490,
				  31508,
				  31619,
				  31629,
				  31715,
				  31805,
				  31815,
				  31816,
				  31817,
				  31842,
				  31912};
				  
  //{
  //}
  //  for (int i =0; i < 1011; i++)
  //    printf("%d\n",sorted_ary[i]);

  for (int i =0; i < 10000; i++)
    {
	 int k = binsearch4(i,sorted_ary,1011);
	 printf("returns: %d \n",k);
    }
		 
  return(0);  
}

/* binsearch:  find x in v[0] <= v[1] <= ... <= v[n-1] */
int binsearch(int x, int v[], int n)
{
       int low, high, mid;
       low = 0;
       high = n - 1;
       while (low < high) {
	    mid = (low+high)/2;
	    if (x < v[mid])
		 high = mid;
	    else if (x > v[mid])
		 if (low!=mid)
		   low = mid;
		 else
		   {
			if (x == v[high])
			  return high;
			return -1;
		   }
	    else    /* found match */
           return mid;
       }
       return -1;   /* no match */
}

/* binsearch:  find x in v[0] <= v[1] <= ... <= v[n-1] */
int binsearch2(int x, int v[], int n)
{
       int low, high, mid;
       low = 0;
       high = n - 1;

       while (low < high)
	  {
	    mid = (low+high)/2;
	    if (x < v[mid])   
		 high = mid;
	    else
		 {
		   if (x == v[mid])
			return mid;
		   if (low != mid)
			low = mid;
		   else
			{ 
			  if (x == v[high])
			    return high;
			  if (x == v[low])
			    return low;
			  return -1;
			}
		 }
	  }
	  return -1;
}


int binsearch3(int x, int v[], int n)
{
       int low, high, mid;
       low = 0;
       high = n - 1;
       while (low < high)
	  {
	    mid = (low+high)/2;
	    if (x < v[mid])
		 {
		   if (mid != high)
			high = mid;
		   else
			break;
		 }
	    else
		 {
		   if (x == v[mid])
			break;
		   else if (low != mid)
			low = mid;
		   else
			break;
		 }
	  }
	  if (x == v[high])
	    return high;
    	  if (x == v[mid])
	    return mid;
	  if (x == v[low])
	    return low;
	  return -1;
}

int binsearch4(int x, int v[], int n)
{
       int low, high, mid;
       low = 0;
       high = n-1;
	  mid = (low+high)/2;
	  
       while ((low < high) && (x != v[mid]) && (mid != high) && (low != mid))
	    {
			if (x < v[mid])
			    high=mid;
			else
			    low=mid;
			mid = (low+high)/2;
	    }
	  
	  if (x == v[high])
	    return high;
    	  if (x == v[mid])
	    return mid;
	  if (x == v[low])
	    return low;
	  return -1;
}
